package seqlist.leetcode;

/**
 * 合并两个排序链表
 *
 * @author yuisama
 * @date 2022/04/24 19:03
 **/
public class Num21_MergeList {
    //    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        // 1.判空
//        if (list1 == null) {
//            return list2;
//        }
//        if (list2 == null) {
//            return list1;
//        }
//        // 此时l1和l2都不为空，开始遍历两个子链表并拼接
//        ListNode dummyHead = new ListNode();
//        // 新链表的尾节点
//        ListNode tail = dummyHead;
//        while (list1 != null && list2 != null) {
//            if (list1.val <= list2.val) {
//                tail.next = list1;
//                tail = list1;
//                list1 = list1.next;
//            }else {
//                tail.next = list2;
//                tail = list2;
//                list2 = list2.next;
//            }
//        }
//        // l1或l2为空
//        if (list1 == null) {
//            // 将l2剩下的节点拼接到新链表尾部
//            tail.next = list2;
//        }
//        if (list2 == null) {
//            tail.next = list1;
//        }
//        return dummyHead.next;
//    }

    /**
     * 传入两个升序链表l1和l2，就能拼接这辆个子链表为一个大的升序链表，返回拼接后的头节点
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1.边界
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }
        list2.next = mergeTwoLists(list1,list2.next);
        return list2;
    }
}